/**
 * 253. 会议室 II
 * https://leetcode-cn.com/problems/meeting-rooms-ii/
 */

/**
 * @param {any[]} arr
 * @param {number} a
 * @param {number} b
 */
function swap(arr, a, b) {
  const temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

/**
 * @param {number[][]} heap
 */
function resolveHeap(heap) {
  if (heap.length <= 1) {
    return;
  }
  for (let i = Math.floor(heap.length / 2) - 1; i >= 0; i -= 1) {
    const val = heap[i][1];
    const left = i * 2 + 1;
    const leftVal = heap[left][1];
    const right = left + 1;
    const rightVal = right >= heap.length ? Infinity : heap[right][1];
    if (val > leftVal || val > rightVal) {
      if (leftVal <= rightVal) {
        swap(heap, i, left);
      } else {
        swap(heap, i, right);
      }
    }
  }
}

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function minMeetingRooms(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const heap = [intervals[0]];
  for (let i = 1; i < intervals.length; i += 1) {
    resolveHeap(heap);
    if (heap[0][1] > intervals[i][0]) {
      heap.push(intervals[i]);
    } else {
      heap[0] = intervals[i];
    }
  }
  return heap.length;
}

console.log(minMeetingRooms([[0, 30], [5, 10], [15, 20]]) === 2);
console.log(minMeetingRooms([[7, 10], [2, 4]]) === 1);
